/// @tags: SAM LCT
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

namespace BlueQuantum {

typedef pair<int, int> PII;

int const N = 1e5 + 5, SAMN = N * 2, M = 2;

int n, m;
char s[N];
int ans[N], end[N];
vector<PII> q[N];

namespace SuffixAutoMaton {

int sam_cnt = 1, lst = 1;
int ch[SAMN][M], link[SAMN], len[SAMN];

inline int extend(int c) {
  int cur = ++sam_cnt, pos = lst;
  lst = cur;
  len[cur] = len[pos] + 1;
  while (pos != 0 && ch[pos][c] == 0) ch[pos][c] = cur, pos = link[pos];
  if (pos == 0) return link[cur] = 1, cur;
  int q = ch[pos][c];
  if (len[q] == len[pos] + 1) return link[cur] = q, cur;
  int nq = ++sam_cnt;
  memcpy(ch[nq], ch[q], sizeof(ch[nq]));
  len[nq] = len[pos] + 1;
  link[nq] = link[q];
  link[q] = link[cur] = nq;
  while (pos != 0 && ch[pos][c] == q) ch[pos][c] = nq, pos = link[pos];
  return cur;
}

}  // namespace SuffixAutoMaton
using SuffixAutoMaton::extend;

namespace SegmentTree {

int tag[N * 4], val[N * 4];

inline void pushup(int x) { val[x] = max(val[x << 1], val[x << 1 | 1]); }

void modify(int x, int l, int r, int p, int v) {
  if (l == r) return tag[x] = max(tag[x], v), val[x] = max(val[x], v), void();
  int mid = (l + r) >> 1;
  if (p <= mid) modify(x << 1, l, mid, p, v);
  if (mid < p) modify(x << 1 | 1, mid + 1, r, p, v);
  pushup(x);
}

int query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return val[x];
  int mid = (l + r) >> 1, res = 0;
  if (L <= mid) res = max(res, query(x << 1, l, mid, L, R));
  if (mid < R) res = max(res, query(x << 1 | 1, mid + 1, r, L, R));
  return res;
}

}  // namespace SegmentTree
using SegmentTree::query;

namespace LinkCutTree {

int ch[SAMN][2], fa[SAMN], col[SAMN], tag[SAMN];

inline bool iden(int x) { return ch[fa[x]][1] == x; }

inline bool isnrt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }

inline void rotate(int x) {
  bool xtofa = iden(x);
  int f = fa[x], gf = fa[f], son = ch[x][!xtofa];
  if (isnrt(f)) ch[gf][iden(f)] = x;
  if (son) fa[son] = f;
  fa[f] = x;
  fa[x] = gf;
  ch[x][!xtofa] = f;
  ch[f][xtofa] = son;
}

inline void pushdown(int x) {
  if (tag[x] != 0) {
    int ls = ch[x][0], rs = ch[x][1];
    col[ls] = col[rs] = tag[x];
    tag[ls] = tag[rs] = tag[x];
    tag[x] = 0;
  }
}

void pushall(int x) {
  if (isnrt(x)) pushall(fa[x]);
  pushdown(x);
}

inline void splay(int x) {
  pushall(x);
  for (; isnrt(x); rotate(x)) {
    if (isnrt(fa[x])) rotate(iden(fa[x]) == iden(x) ? fa[x] : x);
  }
}

inline void access(int x, int color) {
  for (int p = x, y = 0; p; y = p, p = fa[p]) {
    splay(p);
    ch[p][1] = y;
    if (col[p]) SegmentTree::modify(1, 1, n, col[p], SuffixAutoMaton::len[p]);
  }
  splay(x), col[x] = tag[x] = color;
}

}  // namespace LinkCutTree
using LinkCutTree::access;

inline int main() {
  cin >> n >> m;
  cin >> (s + 1);
  for (int i = 1; i <= n; ++i) {
    end[i] = extend(s[i] - '0');
  }
  for (int l, r, i = 1; i <= m; ++i) {
    cin >> l >> r;
    q[r].push_back(make_pair(l, i));
  }
  memcpy(LinkCutTree::fa, SuffixAutoMaton::link, sizeof(LinkCutTree::fa));
  for (int i = 1; i <= n; ++i) {
    access(end[i], i);
    for (vector<PII>::iterator j = q[i].begin(), jlim = q[i].end(); j != jlim; ++j) {
      ans[j->second] = query(1, 1, n, j->first, i);
    }
  }
  for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("similarity.in", "r", stdin);
  freopen("similarity.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
